Masala #0762

Xotira 512 MB Vaqt 1000 ms Qiyinchiligi 97 %

3.6 (Baholar 59)

Persistent Segment Tree (HARD)

Ushbu masalada massivlar soni ko'payib boradi.

Sizga dastlab N va Q mos ravishda N ta elementdan iborat A massiv uzunligi va shu massiv ustida amalga oshiriladigan Q ta so'rovlar soni beriladi, quyidagi so'rovlarning 3-turida massiv yana bittaga ko'payadi.

Sizning vazifangiz quyidagi so'rovlarga javob beruvchi ma'lumotlari tuzilmasini tuzish albatta o'z o'rnida har bir 2-turdagi so'rovga javob qaytarish:

1 ID X Y bu so'rovda siz ID-massivning X-elementini Y ga o'zgartirishing
2 ID L R bu so'rovda siz ID-massivning [L, R] oraliqdagi elementlari yig'indisini chiqarish
3 ID bu so'rovda siz ID-massivda yana bir nusxa oling shunda sizning massivlaringiz soni yana bittaga ko'payadi

Kiruvchi ma'lumotlar:

Birinchi qatorda $N$ va $Q (1 ≤ N, Q ≤ 2 * 10^5)$ butun sonlari mos ravishda massiv elementlari soni va so'rovlar soni.

Keyingi qatorda $N$ ta butun $A[i] (1 ≤ A[i] ≤ 10^9)$ sonlari.

Keyingi $Q$ ta qatorda so'rovlar beriladi.

Chegaralar:
$1 ≤ N, Q ≤ 2 * 10^5$
$1 ≤ A[i], Y ≤ 10^9$
$1 ≤ L ≤ R, X ≤ N$

Chiquvchi ma'lumotlar:

Chiquvchi faylda 2-turdagi so'rovlar uchun mos javobni chiqaring

Misollar

#	input.txt	output.txt
1	3 15 1 2 3 3 1 3 2 3 3 3 4 1 1 1 5 1 2 1 50 1 3 1 500 1 4 1 5000 1 5 1 50000 2 1 1 3 2 2 1 3 2 3 1 3 2 4 1 3 2 5 1 3 3 5	10 55 505 5005 50005

Telegram Facebook

Yechimini yuborish

Bu amalni bajarish uchun tizimga kiring, agar profilingiz bo'lmasa istalgan payt ro'yxatdan o'tishingiz mumkin